/**
 * 代码：12-8
 */


use std::collections::VecDeque;



pub fn max_sliding_window(nums:Vec<i32>, k: i32) -> Vec<i32>
{
    if nums.len() == 0 || k ==1{
        return nums;
    }

    let mut res: Vec<i32> = Vec::new();
    let mut deque :VecDeque<i32> = VecDeque::new();

    for i in 0..nums.len(){

        // 把数组中的值取出送入 双端队列。
        // 双端队列里，检查压入的值和原来的队尾值哪个大，把小的那个值抛掉。把大值从队尾压入。
        push(&mut deque, nums[i]);

        // 滑动窗口超过了窗口值K，就弹出双端队列的队首元素，读取双端队列的队尾值，就是窗口中的最大值
        if (i as i32) > k - 1{
            pop(&mut deque, nums[i-k as usize]);

            res.push(max(&deque));
        } // 在滑动窗口第一次填满时，往res数组中添加一个当前双端队列的最大值。
        else if (i as i32) == k - 1 {
            res.push(max(&deque));


        }
    }

    return  res;
}



fn push(deque: &mut VecDeque<i32>, n: i32){
    while !deque.is_empty() && *deque.back().unwrap() < n {
        deque.pop_back();
    }
    deque.push_back(n);

    print!(" {} push : {:?}\n", n, deque);
}

fn pop(deque: &mut VecDeque<i32>, n: i32)
{
    if !deque.is_empty() && *deque.front().unwrap() == n{
        deque.pop_front();
        print!("pop {} \n", n)
    }
    print!(" n: {}, no pop here \n",n);
}


fn max(deque: &VecDeque<i32>) -> i32
{
    return *deque.front().unwrap();
}


